/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-16
 * Time: 20:50
 */
import java.util.Arrays;
import java.util.PriorityQueue;

public class OptimalServiceOrder {
    public static double[] calculateMinAverageTime(int[] serviceTimes, int serverCount) {
        // 边界处理：无顾客或无服务台，直接返回0
        if (serviceTimes == null || serviceTimes.length == 0 || serverCount <= 0) {
            return new double[]{0.0, 0.0};
        }

        // 1. 对服务时间从小到大排序（核心：短服务优先）
        Arrays.sort(serviceTimes);

        // 2. 用最小堆记录每个服务台的“最早空闲时间”（初始为0，即服务台空闲）
        PriorityQueue<Integer> serverFreeTime = new PriorityQueue<>();
        for (int i = 0; i < serverCount; i++) {
            serverFreeTime.add(0);
        }

        int totalWaitTime = 0; // 所有顾客等待时间总和

        // 3. 为每个顾客分配服务台
        for (int time : serviceTimes) {
            // 取出最早空闲的服务台的空闲时间
            int earliestFree = serverFreeTime.poll();
            // 顾客的等待时间 = 服务台空闲时间（需等服务台空闲才能开始）
            totalWaitTime += earliestFree;
            // 更新该服务台的新空闲时间（空闲时间 + 当前顾客服务时间）
            serverFreeTime.add(earliestFree + time);
        }

        // 计算平均等待时间（总和 / 顾客数量）
        double averageWaitTime = (double) totalWaitTime / serviceTimes.length;
        // 保留2位小数（四舍五入）
        averageWaitTime = Math.round(averageWaitTime * 100.0) / 100.0;

        return new double[]{totalWaitTime, averageWaitTime};
    }

    // 测试示例
    public static void main(String[] args) {
        // 示例1：3个顾客（服务时间[3,1,2]），2个服务台
        int[] times1 = {3, 1, 2};
        int servers1 = 2;
        double[] result1 = calculateMinAverageTime(times1, servers1);
        System.out.println("示例1：总等待时间=" + result1[0] + "，平均等待时间=" + result1[1]);

        // 示例2：5个顾客（服务时间[5,3,4,2,1]），3个服务台
        int[] times2 = {5, 3, 4, 2, 1};
        int servers2 = 3;
        double[] result2 = calculateMinAverageTime(times2, servers2);
        System.out.println("示例2：总等待时间=" + result2[0] + "，平均等待时间=" + result2[1]);

    }
}